The Internet is a set of networks connected by routers. A router maintains a routing table that indicates for each possible destination network, the next hop to which a received data packet should be forwarded. The next hop may be another router or the final destination.
An Internet Protocol (“IP”) data packet received at a port in a router includes an IP destination address. The IP destination address is the final destination of the IP data packet. Currently there are two versions of IP, IP version 4 (“IPv4”) and IP version 6 (“IPv6”). IPv4 provides a 32-bit field in an IP header included in the data packeted for storing the IP destination address. The router forwards a received data packet connected to a next-loop router, or the final destination if the destination is the local network, dependent on the IP destination address stored in the IP header.
A 32-bit IPv4 destination address provides 4 billion possible routes. An Internet router typically stores 50,000 of the 4 billion possible routes. However, the number of stored routes will increase with the growth of the Internet and the widespread use of IPv6.
Originally, the IP address space was divided into three classes of IP addresses; A, B and C. Each IP address space was divided into a network address and a host address. Class A allowed for 126 networks and 16 million hosts per network. Class B allowed for 16382 networks with 64,000 hosts per network and class C allowed for 2 million networks with 256 hosts per network. However, dividing the IP address space into different classes reduced the number of available IP addresses. Class C only allowed a maximum of 256 hosts per network which is too small for most organizations. Therefore, most organizations were assigned a Class B address, taking up 64,000 host addresses which could not be used by other organizations even if they were not used by the organization to which they were assigned. Hosts in an organization with a Class B IP address all store the same network address in the 16 Most Significant Bits (“MBSs”), for example, 128.32.xx.xx.
Classless InterDomain Routing (“CIDR”) was introduced to free up unused IP host addresses. The remaining unused networks are allocated to organization in variable sized blocks. An organization requiring 500 addresses gets 500 continuous addresses. For example, an organization can be assigned 500 available addresses starting at 128.32.xx. The number of routes stored by a router has increased since the introduction of Classless InterDomain Routing. Classless InterDomain Routing requires longest prefix matching to find the corresponding route instead of searching for a matching network address in order to find the corresponding next hop for the IP destination address. For example, a search can no longer stop after the 16 MSBs of a Class B IP address, for example, 128.xx.xx because 128.32.4.xx may be assigned to another organization requiring a different next hop.
One method for searching for a longest prefix match for a key is through the use of a binary tree search. A binary tree search matches a 32-bit input bit by bit down to 32 levels, requiring 32 searches to find the entry matching the 32-bit key. Another method for searching for a match is through the use of a Patricia tree. A Patricia tree reduces the number of searches required if there are no entries down a leaf of the binary tree.
Yet another method for efficiently searching for a next hop associated with an IP destination address is described in PCT application Serial Number PCT/SE98/00854 entitled “Method and System for Fast Routing Lookups” by Brodnick et al. filed on May 11, 1998. The method described by Brodnick reduces the number of next hops stored by not storing duplicate routes. By reducing the number of next hops, the memory requirement is reduced so that a route lookup table can be stored in fast cache memory.
Brodnick et al. divides the binary tree into 3-levels. Dividing the binary tree into 3-levels reduces the number of searches to three. The indexed entry in the first level indicates whether the search can end at the first level with the route taken from the entry, or the search must continue to a subsequent level using a further portion of the IP destination address.
FIG. 1A illustrates a prior art 64K (65536) bit map representing the first level of a binary tree. A 64K bit map 30 represents the leaves or nodes 44 of the binary tree at depth 16, with one bit per node 44. The bit map is divided into bit-masks of length 16. There are 212=4096 bit masks in the 64 k bit map. One bit mask is shown in FIG. 1A. A bit in the bit map 30 is set to ‘1’ if there is a subtree or a route index stored in an array of pointers corresponding to the node 44. A bit in the bit map 30 is set to ‘0’ if the node shares a route entry with a previous node 44.
A bit is set in the bit map 30 if the node does not share the route entry the previous node 44. Bit 4 is set ‘1’ indicating that there is a subtree or route index corresponding to the node 44. Bit 5 is set ‘0’ indicating that the node corresponding to bit 5 shares the subtree or route index with the node corresponding to bit 4. Bit 6 is set ‘1’ indicating that the node corresponding to bit 6 does not share a subtree or route index with bits 4 and 5. Bit 6 corresponds to a node sharing the default route. Bits 6 and 12 set to ‘1’ correspond to the default route.
FIG. 1B illustrates a prior art lookup table implemented in cache memory. The lookup table includes an array of code words 36, an array of base indices 34 and a map table 40. A 32-bit IP address 38 is also shown in FIG. 1B. A codeword 46 is stored in the array of code words 36 for each bit mask in the bit map 30 (FIG. 1A). The code word 46 includes a six-bit value 46a and a 10-bit offset 46b. A base index 42 is stored in the array of base indices 34 for every four code words 46 in the array of code words 36.
The array of code words 36, array of base indices 34 and map table 40 are used to select a pointer in an array of pointers (not shown). The pointer stores a route index or an index to perform a further search.
A group of pointers in the array of pointers is selected by selecting a code word 46 in the array of code words 36 and a base index 42 in the array of base indices 34. The code word 46 is selected using the first 12 bits 50 of the IP address 38. The base index 42 is selected using the first 10 bits 48 of the IP address 38. The correct pointer in the group of pointers is selected using the map table 32.
The 10-bit value 46b in the selected code word 36 is an index into the map table 32. The map table 32 maps bit numbers within a bit-mask to 4-bit offsets. The offset specifies the pointer within the selected group of pointers in the array of pointers. The 10-bit value 46b selects the row in the map table 32 and bits 19:16 of the IP address 52 selects the 4-bit offset 54.
An offset to specify a pointer is stored in the map table 32 for each ‘1’ stored in the bit mask 30 (FIG. 1A). Thus, two separate location offsets to specify a default pointer corresponding to bits 6 and 12 in the bit mask 30 are stored in two separate locations in the map table 32. Storing multiple copies of the default pointer in the array of pointers reduces the number of route indexes that can be stored in a fixed size memory.
FIG. 2A illustrates a worst case encoded subtree which requires twice the number of entries in the array of pointers than actual routes. The routes r1-r8 are assigned to leaf nodes 215, 217, 219, 221, 223, 225, 227 and 229 as follows: r1 to leaf node 215; r2 to leaf node 217, r3 to leaf node 219; r4 to leaf node 221; r5 to leaf node 223; r6 to leaf node 225; r7 to leaf node 227 and r8 to leaf node 229. The default route r0 is assigned to all of the other leaf nodes 216, 218, 220, 222, 224, 226, 228 and 230.
FIG. 2B illustrates a prior art bit map 30 and associated pointers stored in an array of pointers 50 representative of the subtree shown in FIG. 2A. As described in conjunction with FIG. 1A, the bit map 30 includes one bit 2421-24216 for each leaf node in the subtree. The array of pointers 50 stores a pointer for each bit set to ‘1’ in the bit map 30. A bit is set ‘1’ to indicate that the route corresponding to the leaf node differs from the route stored for the previous leaf node in the map table 32.
Sixteen entries are used to store the eight pointers to routes r1-r8 and the default route r0. The pointer to the default route r0 is stored in eight of the sixteen entries 2521-16.
A route corresponding to a node in the subtree is found by counting the number of ‘1’s in the bit map and incrementing the pointer by the total number of ones. For example, the entry corresponding to node 224 (FIG. 2A) is stored in entry 25212. Storing the pointer to the default route in eight different entries decreases the available memory for storing pointers to routes.